package leetcode_day._2022._202209._0110;

import java.util.Arrays;
import java.util.Comparator;

/**
 * 646. 最长数对链
 * 算法：排序 + 动态规划、排序 + 贪心
 *
 * @author yzh
 * @version 1.0
 * @date 2022/9/4 18:09
 */
public class _03 {

    public int findLongestChain(int[][] pairs) {
        Arrays.sort(pairs, Comparator.comparingInt(a -> a[0]));
        int n = pairs.length, ans = 0;
        int[] dp = new int[n];
        for (int i = 0; i < n; i++) {
            dp[i] = 1;
            for (int j = i - 1; j >= 0 && dp[i] == 1; j--)
                if (pairs[i][0] > pairs[j][1]) dp[i] = dp[j] + 1;
            ans = Math.max(ans, dp[i]);
        }
        return ans;
    }

    public int findLongestChainUpgrade(int[][] pairs) {
        Arrays.sort(pairs, Comparator.comparingInt(a -> a[0]));
        int n = pairs.length, ans = 0;
        int[] g = new int[n + 10];
        Arrays.fill(g, 0x3f3f3f3f);
        for (int i = 0; i < n; i++) {
            int l = 1, r = i + 1;
            while (l < r) {
                int mid = l + r >> 1;
                if (g[mid] >= pairs[i][0]) r = mid;
                else l = mid + 1;
            }
            g[l] = Math.min(g[l], pairs[i][1]);
            ans = Math.max(ans, l);
        }
        return ans;
    }

    public int findLongestChainUpgradeGreedy(int[][] pairs) {
        Arrays.sort(pairs, Comparator.comparingInt(a -> a[1]));
        int ans = 1;
        int[] tmp = pairs[0];
        for (int i = 1; i < pairs.length; i++) {
            if (pairs[i][0] > tmp[1]) {
                ++ans;
                tmp = pairs[i];
            }
        }
        return ans;
    }

}
